package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/26 15:49
 */
public class E1005 {

    /**
     * <h3>方法一：老老实实遍历</h3>
     *
     * @param nums 数组
     * @param k    找k次最小值取反
     * @return 结果数组之和
     */
    public int largestSumAfterKNegations1(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            int minIndex = minIndex(nums);
            nums[minIndex] = -nums[minIndex];
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // return Arrays.stream(nums).sum(); 效率不好
        return sum;
    }

    /**
     * 寻找最小值的下标
     *
     * @param nums 数组
     * @return 最小值的下标
     */
    private int minIndex(int[] nums) {
        int minIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[minIndex]) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    /**
     * <h3>方法二：用排序的方式</h3>
     *
     * @param nums 数组
     * @param k    找k次最小值取反
     * @return 结果数组之和
     */
    public int largestSumAfterKNegations2(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < k; i++) {
            nums[0] = -nums[0];
            // 将第一个元素在进行一次插入排序
            insertOne(nums);
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum;
    }

    /**
     * 只对第一个元素进行插入排序
     *
     * @param nums 数组
     */
    private void insertOne(int[] nums) {
        int insert = nums[0];
        int index = 1;
        while (index < nums.length) {
            if (nums[index] < insert) {
                nums[index - 1] = nums[index];
                index++;
            } else break;
        }
        nums[index - 1] = insert;
    }

    /**
     * <h3>方法三：用排序的方式，思路与方法二不同，排序次数减少</h3>
     *
     * @param nums 数组
     * @param k    找k次最小值取反
     * @return 结果数组之和
     */
    public int largestSumAfterKNegations3(int[] nums, int k) {
        int sum = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 核心思想是尽可能将所有的负数取反
            // 情况1：负数个数 == 0  那只能是最小的正数反复取反k次，k为偶数则不变，k为奇数则取反
            // 情况2：负数个数 <  k  将所有负数取反后，让最小的正数反复取反k次，k为偶数则不变，k为奇数则取反
            // 情况3：负数个数 >= k  将最小的的k个负数取反既是结果
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
            // 累加
            sum += nums[i];
        }
        // 再次排序，方便后面找最小值
        Arrays.sort(nums);
        // k为奇数则减去2倍最小值，偶数则不变
        return (k & 1) == 0 ? sum : sum - 2 * nums[0];
    }

    /**
     * <h3>方法四：用计数排序的思想，因为题目限制-100 <= nums[i] <= 100 1ms</h3>
     *
     * @param nums 数组
     * @param k    找k次最小值取反
     * @return 结果数组之和
     */
    public int largestSumAfterKNegations4(int[] nums, int k) {
        // 计算最终的累加和
        int sum = 0;
        // count数组，记录每个元素的出现次数
        int[] count = new int[201];
        // 对count数组赋初值
        for (int num : nums) {
            count[num + 100]++;
        }
        // 先对负数进行处理
        int index = 0;
        while (index < 100) {
            // 当前最小的负数出现次数不为0且k不为0时，将当前元素取反，k--
            while (count[index] != 0 && k > 0) {
                count[index]--;
                count[200 - index]++;
                k--;
            }
            // 在遍历完所有负数之前，k变为了0，直接跳出循环，index停留在当前负数（当前负数可能还有出现次数）
            if (k == 0) {
                break; // 当最后一个负数如果为-1且出现，处理完恰好k为0，则index停留在99
            }
            // k不为0，继续处理下一个最小的负数，如果遍历完所有负数，k不为0，则index停留在100，也就是0
            index++;
        }
        // 当剩余的k为奇数，也就是k没有用完且为奇数，则减去一个正数的最小值即可
        if ((k & 1) == 1) {
            while (index < 201) {
                if (count[index] > 0) {
                    count[index]--;
                    sum -= index - 100;
                    break; // 退出时索引应当是当前最小正数索引
                }
                index++;
            }
        }
        // 从当前最小正数索引开始或者是从剩下的最小的负数的索引开始，进行累加求和
        for (int i = index; i < 201; i++) {
            sum += count[i] * (i - 100);
        }
        // 返回结果
        return sum;
    }

    /**
     * <h3>方法五：用计数排序的思想，但是对负数、正数分别用一个count</h3>
     *
     * @param nums 数组
     * @param k    找k次最小值取反
     * @return 结果数组之和
     */
    public int largestSumAfterKNegations5(int[] nums, int k) {
        int[] positiveCount = new int[101];
        int[] negativeCount = new int[101];

        int cntS = 0, sumS = 0, sumP = 0;
        for (int x : nums) {
            if (x <= 0) {
                negativeCount[-x]++;
                cntS++;
                sumS += x; // 统计负数的和
            } else {
                positiveCount[x]++;
                sumP += x; // 统计正数的和
            }
        }

        if (k >= cntS) {
            if ((k - cntS) % 2 == 0) {
                return sumP - sumS; // k大于或等于负数的数量，且剩余的k为偶数
            } else {
                int tempx = 0;
                for (int i = 0; i <= 100; i++) {
                    if (positiveCount[i] != 0 || negativeCount[i] != 0) {
                        tempx = i; // 找到最小的正数
                        break;
                    }
                }
                return sumP - sumS - tempx - tempx; // 取反最小的正数
            }
        } else {
            int tempSum = 0, tempK = k;
            int i = 100;
            while (tempK > 0) {
                if (negativeCount[i] == 0) {
                    i--;
                    continue;
                } else {
                    negativeCount[i]--;
                    tempK--;
                    tempSum += i; // 计算取反负数的总和
                }
            }
            return sumP + tempSum + (sumS - (-tempSum)); // 返回正数和与取反后负数和的总和
        }
    }
}
